#define  _CRT_SECURE_NO_WARNINGS
// class Solution {
//     int quickSort(vector<int>& nums, int left, int right, int k)
//     {
//         if(left >= right) return nums[right];
//         int i = left - 1, j = right + 1, key = nums[(left + right) >> 1];
//         while(i < j)
//         {
//             do ++i; while(nums[i] < key);
//             do --j; while(nums[j] > key);
//             if(i < j)swap(nums[i],nums[j]);
//         }
//         if(j + 1 >= k) return quickSort(nums, left, j, k);
//         else return quickSort(nums, j + 1, right, k);
//     }
// public:
//     int findKthLargest(vector<int>& nums, int k) {
//         return quickSort(nums, 0, nums.size() - 1, nums.size() - k + 1);
//     }
// };

class Solution {
    int quickSort(vector<int>& nums, int left, int right, int k)
    {
        if (left >= right) return nums[left];
        int i = left, cur = left, j = right, key = nums[rand() % (right - left + 1) + left];
        while (cur <= j)
        {
            if (nums[cur] < key) swap(nums[i++], nums[cur++]);
            else if (nums[cur] > key) swap(nums[j--], nums[cur]);
            else cur++;
        }
        int A = i - left, B = j - i + 1, C = right - j;
        if (C >= k) return quickSort(nums, j + 1, right, k);
        if (C + B >= k) return nums[i];
        return quickSort(nums, left, i - 1, k - C - B);
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        return quickSort(nums, 0, nums.size() - 1, k);
    }
};